package linkedList;

/**
 * 234. 回文链表
 *
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
 * 如果是，返回 true ；否则，返回 false 。
 *
 * 提示：
 *
 * 链表中节点数目在范围[1, 105] 内
 * 0 <= Node.val <= 9
 * 进阶：你能否用O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 *
 */

public class PalindormeLinkedList_234 {
    // 位运算不太靠谱，例如 5,3,6，^之后结果为0
    public boolean isPalindrome2(ListNode head) {
        if (head.next == null) {
            return true;
        }

        int flag = head.val;
        head = head.next;
        while (head != null) {
            flag = flag ^ head.val;
            head = head.next;
        }
        return flag == 0;
    }

    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 需要反转前半段链表，但这次不需要dummy节点
        ListNode prev = null;
        // slow达到链表的中点，遍历过程中反转链表
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = head;
            head = head.next;
            slow.next = prev;
            prev = slow;
        }

        // head指针从中点开始向前遍历，slow指针从中点开始向后遍历
        // 如果fast是null，表示有偶数个节点
        // 如果fast不是null，表示有奇数个节点，head指针需要前进一步
        if (fast != null) {
            head = head.next;
        }

        while (head != null) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}
